package com.desheng.bigdata.ds.sort;

import java.util.Arrays;

/**
 * 排序，默认都是做升序的排序
 * 笔试题：不使用第三方变量，交换两个数，请使用三种方式
 * 第一种：异或^
 * 第二种：
 */
public class MySort {
    public static void main(String[] args) {
        int arr[] = {10, 9, -2, 6, 7, 1, 3, 8, 0};

        System.out.println("排序前的数组：" + Arrays.toString(arr));
//        selectSort(arr);
//        insertSort(arr);
        quickSort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }

    /**
     * 快速排序：
     * @param arr
     */
    private static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    //重载函数
    private static void quickSort(int[] arr, int low, int high) {
        if(low >= high) {//这一点主要是用于剔除low=arr.length-1的情况，防止数组越界
            return;
        }

        int start = low + 1;
        int end = high;
        int mark = arr[low];//基准元素值

        //要开始找右侧比基准元素小的元素
        //从左侧找比基准元素大的元素
        while (start < end) {
            while(start < end && arr[end] > mark) {//找到一个比基准元素小的元素
                end--;
            }
            while (start < end && arr[start] < mark) {//找到一个比基准元素大的有时怒
                start++;
            }
            //arr[end]比基准元素小，arr[start]比基准元素大，二者交换
            if(start < end) {
                swap(arr, start, end);
            }
        }
        //到这里，说明数组已经成为了两半儿，左侧都比基准元素小，右侧的都比基准元素大，现在只需要定位基准元素的位置即可
        arr[low] = arr[start];
        arr[start] = mark;
        //进行基准元素左侧的比较
        quickSort(arr, low, start - 1);
        //进行基准元素右侧的比较
        quickSort(arr, start + 1, high);
    }

    /**
     * 插入排序：
     *      将一个元素插入到一个有序的序列中，使之成为一个有序的序列。
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {//控制循环多少趟
            for(int j = i + 1; j > 0; j--) {
                if(arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }
    /**
     * 选择排序
     * @param arr
     */
    private static void selectSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {//控制循环多少趟
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]) {
                    /*int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;*/
                    swap(arr, i, j);
                }
            }
        }
    }

    /**
     * 两个二进制的操作符可能出现的操作组合：
     * 1 0
     * 0 1
     * 0 0
     * 1 1
     * 按位
     * &（按位与） 除了两个操作符为1以外，其它操作结果都为0
     *  1 & 0 = 0
     *  1 & 1 = 1
     *  0 & 0 = 0
     *  0 & 1 = 0
     * |（按位或） 只要有一个为1，就为1，
     *  1 | 0 = 1
     *  1 | 1 = 1
     *  0 | 0 = 0
     *  0 | 1 = 1
     * ^（异或）相同为0，不同为1：
     *  1 ^ 0 = 1
     *  1 ^ 1 = 0
     *  0 ^ 0 = 0
     *  0 ^ 1 = 1
     * ~（非，或者取反，是一个单目运算符）
     *  ~1 = 0
     *  ~0 = 1
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
        //下面这种方式，可能出现越界的问题
       /* arr[i] = arr[i] + arr[j];
        arr[j] = arr[i] - arr[j];
        arr[i] = arr[i] - arr[j];*/
    }

    private static <T> void swap(T[] arr, int i, int j) {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static <T extends Comparable<T>> void insertSort(T[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {//控制循环多少趟
            for(int j = i + 1; j > 0; j--) {
                if(arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }
}
